package seqlist.LeetCode;
//160. 相交链表
//给你两个单链表的头节点 headA 和 headB ，
// 请你找出并返回两个单链表相交的起始节点。
// 如果两个链表不存在相交节点，返回 null 。

/**
 * 思路一：路径相等。
 * 我们假设A链表不相等的为 a ，相等路径为 c
 * 我们假设B链表不相等的为 b ，相等路径为 c
 * 整个A链表路径 = a + c， 整个B链表路径 = b + c
 * 如果此时引入两个指针，指针A走完A链表路径再走B链表不相等路程
 * 指针B走完B链表路径再走A链表不相等路程
 * 两个指针的总路径为： a + c + b = b + c + a; 如果它们相交，此刻肯定在
 * 第一个相交的节点上，因为路径相等。
 * 如果是不想交的话此刻两个链表值都为 null
 */
public class Num160_getIntersectionNode {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode l1 = headA;
        ListNode l2 = headB;

        //地址相等的话就结束循环
        while(l1 != l2){
            l1 = (l1 == null) ? headB : l1.next;
            l2 = (l2 == null) ? headA : l2.next;
        }

        //走到null什么不相交
        if(l1 == null ){
            return null;
        }

        return l1;
    }

}
